/*
	aco-netdesign -- Ant colony optimization solution to network design problem

	Copyright (C) 2008 Jeffrey Sharkey, http://jsharkey.org/
	
	Developed by Jeffrey Sharkey as part of his thesis work at Montana State
	University. His work was sponsored by the Western Transportation Institute,
	and was guided by advisor Doug Galarus. Other valuable guidance was
	provided by Dr. Bill Jameson and Gary Schoep. 

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "solver.h"




Solution::Solution() : Path(NULL, NULL) {
	vertexes.clear();
	invalid = false;
}

Solution::~Solution() {
}



void Solution::saveSimple(Graph* g, string filename) {

	ofstream out(filename.c_str(), ofstream::out);
	out.precision(8);


	out << "<?xml version=\"1.0\" encoding=\"Windows-1252\"?><kml xmlns=\"http://earth.google.com/kml/2.0\"><Document>" << endl;
	out << "<Style id=\"layer1\"><IconStyle><color>ff0000ff</color><colorMode>normal</colorMode><scale>3.0</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/triangle.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
	out << "<Style id=\"layer2\"><IconStyle><color>ff00ff00</color><colorMode>normal</colorMode><scale>2.0</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/circle.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
	out << "<Style id=\"layer3\"><IconStyle><color>ffff0000</color><colorMode>normal</colorMode><scale>1.0</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/square.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
	out << "<Style id=\"edges\"><LineStyle><color>88ffffff</color><colorMode>normal</colorMode><width>4</width></LineStyle></Style>" << endl;
	
	ulist<Vertex*>::iterator i;
	for(i = vertexes.begin(); i != vertexes.end(); i++) {
		Vertex* v = (*i);
		if(v->root) continue;
		out << "<Placemark><styleUrl>#layer" << v->layer << "</styleUrl><Point><coordinates>" << v->kmlString(50) << "</coordinates></Point></Placemark>" << endl;
	}

	ulist<Edge*>::iterator j;
	for(j = edges.begin(); j != edges.end(); j++) {
		Edge* e = (*j);
		if(e->u->root || e->v->root) continue;
		out << "<Placemark><styleUrl>#edges</styleUrl><LineString><altitudeMode>relativeToGround</altitudeMode><coordinates>" << e->u->kmlString(50) << " " << e->v->kmlString(50) << "</coordinates></LineString></Placemark>" << endl;
	}
	
	out << "</Document></kml>" << endl;
	out.close();
	


}


void Solution::save(Graph* g, string filename) {
	
	ofstream out(filename.c_str(), ofstream::out);
	out.precision(8);
	
	out << "<?xml version=\"1.0\" encoding=\"Windows-1252\"?><kml xmlns=\"http://earth.google.com/kml/2.0\"><Document>" << endl;
	out << "<Style id=\"back\"><IconStyle><color>ffffffff</color><colorMode>normal</colorMode><scale>1.0</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/triangle.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
	out << "<Style id=\"thin\"><LineStyle><color>00ffffff</color><colorMode>normal</colorMode><width>1</width></LineStyle></Style>" << endl;
	
	// dump out color information
	int color = 0;
	int colorCount = 4;
	string colors[colorCount];

	colors[0] = "ff29e23f"; colors[1] = "ff13a9ff"; colors[2] = "ffe28329";
	colors[3] = "ff2929e2"; //colors[4] = "ffe3e329"; colors[5] = "ffe329a5";

	string colorname[colorCount];
	colorname[0] = "green"; colorname[1] = "orange"; colorname[2] = "blue";
	colorname[3] = "red"; //colorname[4] = "teal"; purple

//	colors[0] = "ff0000ff"; colors[1] = "ff00ff00"; colors[2] = "ffff0000";
//	colors[3] = "ff00ffff"; colors[4] = "ffff00ff"; colors[5] = "ffffff00";
	
/*
	for(int i = 0; i < colorCount; i++) {
		out << "<Style id=\"road" << i << "\"><IconStyle><color>" << colors[i] << "</color><colorMode>normal</colorMode><scale>0.8</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/triangle.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
		out << "<Style id=\"term" << i << "\"><LineStyle><color>" << colors[i] << "</color><colorMode>normal</colorMode><width>4</width></LineStyle></Style>" << endl;
	}
*/
	
	// dump out list of all steiner nodes, and assign colors if on layer 2
	map<Vertex*,int> nodeColors;
	list<Vertex*> roadsides;
	ulist<Vertex*>::iterator j;
	for(j = vertexes.begin(); j != vertexes.end(); j++) {
		Vertex* v = (*j);

		switch(v->layer) {
			case 1:
				out << "<Placemark><styleUrl>#back</styleUrl><Point><coordinates>" << v->kmlString() << "</coordinates></Point></Placemark>" << endl;
				break;
			
			case 2:
				// assign next color to this layer 2 node
				color++;

				out << "<Style id=\"road" << color << "\"><!-- " << colorname[color % colorCount] << " --><IconStyle><color>" << colors[color % colorCount] << "</color><colorMode>normal</colorMode><scale>0.8</scale><Icon><href>http://maps.google.com/mapfiles/kml/shapes/triangle.png</href></Icon></IconStyle><LabelStyle><scale>0</scale></LabelStyle></Style>" << endl;
				out << "<Style id=\"term" << color << "\"><LineStyle><color>" << colors[color % colorCount] << "</color><colorMode>normal</colorMode><width>4</width></LineStyle></Style>" << endl;

				roadsides.push_back(v);
				nodeColors[v] = color;
				out << "<Placemark><name>color" << color << "</name><styleUrl>#road" << nodeColors[v] << "</styleUrl><Point><altitudeMode>relativeToGround</altitudeMode><coordinates>" << v->kmlString(50) << "</coordinates></Point></Placemark>" << endl;
				break;
		}
	}
	
	// assign each terminal node their closest parent
	//map<Vertex*,Vertex*> parents;
	ulist<Vertex*>::iterator i;
	string last("");
	for(i = g->terminal.begin(); i != g->terminal.end(); i++) {
		// find the closest layer 2 vertex selected
		Vertex* terminal = (*i);
		if(terminal->root) continue;
		Vertex* roadside = NULL;
		double roadsideDist = LARGE_COST;
		
//cout << "--" << endl;
		list<Vertex*>::iterator j;
		for(j = roadsides.begin(); j != roadsides.end(); j++) {
			Vertex* consider = (*j);
			// if we are at same location then accept
			if(consider->lat == terminal->lat && consider->lon == terminal->lon) {
//cout << "FOUND EXACT MATCH!" << endl;
				roadside = consider;
				break;
			}

			// consider only if edge exists
			if(!g->edgeExists(terminal, consider)) continue;
			
			// keep track of closest roadside vertex
			double considerDist = terminal->distance(consider);
//cout << "distance = " << considerDist << endl;
			if(considerDist < roadsideDist || isnan(considerDist)) {
				roadside = consider;
				roadsideDist = considerDist;
			}
		}
		
		// assign closest roadside vertex as parent
//if(roadside == NULL) continue;
		assert(roadside != NULL);
		//parents[terminal] = roadside;
		
		if(last == "") last = terminal->kmlString();
		
		out << "<Placemark><styleUrl>#thin</styleUrl><LineString><altitudeMode>relativeToGround</altitudeMode><coordinates>" << terminal->kmlString() << " " << roadside->kmlString(50) << "</coordinates></LineString></Placemark>" << endl;
		out << "<Placemark><styleUrl>#term" << nodeColors[roadside] << "</styleUrl><LineString><coordinates>" << last << " " << terminal->kmlString() << "</coordinates></LineString></Placemark>" << endl;
		
		last = terminal->kmlString();
		
	}
	
	out << "</Document></kml>" << endl;
	out.close();
	
}


void Solution::saveRaw(Graph* g, string filename) {
	
	ofstream out(filename.c_str(), ofstream::out);
	out.precision(8);

	// dump out raw tower assignments
	list<Vertex*> roadsides;
	ulist<Vertex*>::iterator j;
	for(j = vertexes.begin(); j != vertexes.end(); j++) {
		Vertex* v = (*j);
		switch(v->layer) {
			case 2:
				// assign next color to this layer 2 node
				roadsides.push_back(v);
				break;
		}
	}


	// assign each terminal node their closest parent
	//map<Vertex*,Vertex*> parents;
	ulist<Vertex*>::iterator i;
	string last("");
	for(i = g->terminal.begin(); i != g->terminal.end(); i++) {
		// find the closest layer 2 vertex selected
		Vertex* terminal = (*i);
		if(terminal->root) continue;
		Vertex* roadside = NULL;
		double roadsideDist = LARGE_COST;
		
		list<Vertex*>::iterator j;
		for(j = roadsides.begin(); j != roadsides.end(); j++) {
			Vertex* consider = (*j);
			// consider only if edge exists
			if(!g->edgeExists(terminal, consider)) continue;
			
			// keep track of closest roadside vertex
			double considerDist = terminal->distance(consider);
			if(considerDist < roadsideDist) {
				roadside = consider;
				roadsideDist = considerDist;
			}
		}
		
		// assign closest roadside vertex as parent
if(roadside == NULL) continue;
		assert(roadside != NULL);
		//parents[terminal] = roadside;
		
		out << terminal->kmlString() << "\t" << roadside->kmlString() << endl;
		
	}

	out.close();


}





Solver::Solver(Graph* g_, Lookup* look_) : g(g_), look(look_) {
}

Solver::~Solver() {
}




SolverApprox::SolverApprox(Graph* g_, Lookup* look_) : Solver(g_, look_) {
}

SolverApprox::~SolverApprox() {
}

Solution* SolverApprox::singleSolution() {
	Solution* s = new Solution();
	
cout << "singleSolution: making copy of terminal nodes" << endl; cout.flush();
	// make list of all terminal nodes we need to satisfy
	ulist<Vertex*> S = g->terminal;
	
	// pop first terminal vertex and add to solution
cout << "singleSolution: popping first item" << endl; cout.flush();
	Vertex* v = S.front();
	S.erase(S.begin());
	s->vertexes.insert(v);
	
cout << "singleSolution: starting loop" << endl; cout.flush();
	TimeRemaining* t = new TimeRemaining(S.size(), 32);
	while(S.size() > 0) {


		
		// find the next-best terminal vertex to connect
		Vertex* finalTerminal = NULL;
		Vertex* finalTree = NULL;
		double finalCost = LARGE_COST;
		
		ulist<Vertex*>::iterator i;
		for(i = S.begin(); i != S.end(); i++) {
			Vertex* terminal = (Vertex*)(*i);
			
			// find cheapest way to link back into existing tree
			Vertex* bestTree = NULL;
			double bestCost = LARGE_COST;
			
			ulist<Vertex*>::iterator j;
			for(j = s->vertexes.begin(); j != s->vertexes.end(); j++) {
				Vertex* tree = (Vertex*)(*j);
				
				double cost = look->get(terminal, tree);
				if(cost < bestCost) {
					bestTree = tree;
					bestCost = cost;
				}
			}
			
			// keep track of overall best terminal-to-tree link
			if(bestCost < finalCost) {
				finalTerminal = terminal;
				finalTree = bestTree;
				finalCost = bestCost;
			}
		}

//if(finalTerminal == NULL) break;
		
		assert(finalTerminal != NULL);
		assert(finalTree != NULL);
		
		// add the final best link between terminal and tree
		// construct and add shortest path between two points
		Path* p = look->shortestPath(finalTerminal, finalTree);
		s->merge(p);
		
		// remove terminal chosen from our remaining list
		for(i = S.begin(); i != S.end(); i++) {
			if(*finalTerminal == **i) {
				S.erase(i);
				break;
			}
		}
		
		t->increment();
		
	}
	
	return s;
}



